Corelab Seminar
2015-2016
Paris Syminelakis
Symmetric Graph Properties Have Independent Edges
Abstract.
In the study of random structures we often face a trade-off between realism and tractability, the latter typically enabled by independence assumptions. In this work we initiate an e ffort to bridge this gap by developing tools that allow us to work with independence without assuming it. Let G_n be the set of all graphs on n vertices and let S be an arbitrary subset of G_n, e.g., the set of all graphs with m edges. The study of random networks can be seen as the study of properties that are true for most elements of S, i.e., that are true with high probability for a uniformly random element of S. With this in mind, we pursue the following question:
"what are general sufficient conditions for the uniform measure on a set of graphs S \subset G_n to be well-approximable by a product measure on the set of all possible edges?"
This is joint work with Dimitris Achlioptas (UC Santa Cruz) and appeared in ICALP'2015.